//
// Created by bleedingfight on 2020/7/5.
//
#include "frequencySort.h"

using namespace std;

std::string frequencySort(std::string s) {
    std::map<char, int> char_frequency;
    std::string result;
    vector<char> freq = vector<char>(s.length(), '\0');
    for (auto ch:s)
        char_frequency[ch] += 1;

    auto fn = [](pair<char, int> a1, pair<char, int> a2) { return a1.second < a2.second; };
    std::priority_queue<pair<char, int>, std::vector<pair<char, int>>, decltype(fn)> current_frequency(fn);
    for (auto e:char_frequency)
        current_frequency.push(pair<char, int>(e.first, e.second));

    while (!current_frequency.empty()) {
        auto elem = current_frequency.top();
        for (int i = 0; i < elem.second; i++)
            result += elem.first;
        current_frequency.pop();
    }
    return result;
}
